UVa/11512 - GATTACA/gattaca.2.cpp

   1 /*
   2   Problem: G - GATTACA
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6   Naive
   7  */
   8
   9 using namespace std;
  10 #include <algorithm>
  11 #include <iostream>
  12 #include <iterator>
  13 #include <sstream>
  14 #include <fstream>
  15 #include <cassert>
  16 #include <climits>
  17 #include <cstdlib>
  18 #include <cstring>
  19 #include <string>
  20 #include <cstdio>
  21 #include <vector>
  22 #include <cmath>
  23 #include <queue>
  24 #include <deque>
  25 #include <stack>
  26 #include <map>
  27 #include <set>
  28
  29 #define D(x) cout << #x " is " << x << endl
  30
  31 int main(){
  32   //freopen("gattaca.in", "r", stdin);
  33   int T;
  34   cin >> T;
  35   while (T--){
  36     string s;
  37     cin >> s;
  38     int n = s.size(), rep = 0;
  39     string ans = "";
  40     map<string, int> cnt;
  41     for (int i=0; i<n; ++i){
  42         string so_far = "";
  43         for (int j=i; j < n; ++j){
  44           so_far += s[j];
  45           int t = ++cnt[so_far];
  46           if (t > 1 && (so_far.size() > ans.size() || (so_far.size() == ans.size() && so_far < ans))){
  47             ans = so_far;
  48             rep = t;
  49           }
  50         }
  51       }
  52            if (rep == 0) cout << "No repetitions found!\n";
  53            else cout << ans << " " << rep << endl;
  54   }
  55   return 0;
  56 }